package com.fs.leetcode.array;

import com.google.common.collect.Lists;

import java.util.List;

/**
 * @author shuai.fang
 * @date：2018-01-25
 * @description：在一个排序好的数组里面删除重复的元素。
 */
public class RemoveDuplicatesFromSortedArray {

	public static void main(String[] args) {
		int[] array = new int[] {1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 6, 7, 7, 8};
		removeDuplicatesElementFromSortedArray(array);

		removeDuplicatesElementFromSortedArrayAndCanSpecialDuplicateNumber(array, 2);
		removeDuplicatesElementFromSortedArrayAndCanSpecialDuplicateNumber2(array, 2);
	}

	/**
	 * 假定为升序排列, 前一位和后一位相比
	 * {1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 6, 7, 7, 8}
	 * {1, 2, 3, 4, 5, 6, 7, 8}
	 * @param array
	 */
	public static void removeDuplicatesElementFromSortedArray(int[] array) {
		List<Integer> list = Lists.newArrayList();
		list.add(array[0]);
		int lastNoRepeatIndex = 0;
		for (int i = 1; i < array.length; i++) {
			if (array[lastNoRepeatIndex] == array[i]) {
				continue;
			}
			list.add(array[i]);
			lastNoRepeatIndex = i;
		}
		System.out.println("删除完重复的元素后的数组为 -> " + list);
	}

	/**
	 * 移除重复的元素，但是可以允许最多指定重复元素存在。
	 * {1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 6, 7, 7, 8}  2
	 * result [1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8]
	 * @param array
	 * @param canDuplicateNumber
	 */
	public static void removeDuplicatesElementFromSortedArrayAndCanSpecialDuplicateNumber(int[] array, int canDuplicateNumber) {
		List<Integer> list = Lists.newArrayList();
		list.add(array[0]);
		int lastIndex = 0;
		int repeatCount = 1;
		int lastValue = array[0];
		for (int i = 1; i < array.length; i++) {
			if (array[lastIndex] == array[i]) {
				if (repeatCount++ >= canDuplicateNumber) {
					continue;
				}
			}
			list.add(array[i]);
			lastIndex = i;
			if (lastValue != array[i]) {
				repeatCount = 1;
				lastValue = array[i];
			}
		}
		System.out.println("第一种方法：指定可重复元素数为 -> " + canDuplicateNumber + ", 删除后的数据元素为 -> " + list);
	}

	/**
	 * 移除重复的元素，但是可以允许最多指定重复元素存在。
	 * {1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 5, 5, 6, 7, 7, 8}  2
	 * result [1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8]
	 * @param array
	 * @param canDuplicateNumber
	 */
	public static void removeDuplicatesElementFromSortedArrayAndCanSpecialDuplicateNumber2(int[] array, int canDuplicateNumber) {
		List<Integer> list = Lists.newArrayList();
		int j = 0;
		int num = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[j] == array[i]) {
				if (num < canDuplicateNumber) {
					list.add(array[i]);
					num++;
					System.out.println(num);
				}
			} else {
				list.add(array[i]);
				j = i;
				num = 1;
			}
		}
		System.out.println("第二种方法：指定可重复元素数为 -> " + canDuplicateNumber + ", 删除后的数据元素为 -> " + list);
	}

}
